// 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

// 例如，

// [2,3,4] 的中位数是 3

// [2,3] 的中位数是 (2 + 3) / 2 = 2.5

// 设计一个支持以下两种操作的数据结构：

// void addNum(int num) - 从数据流中添加一个整数到数据结构中。
// double findMedian() - 返回目前所有元素的中位数。
// 示例：

// addNum(1)
// addNum(2)
// findMedian() -> 1.5
// addNum(3) 
// findMedian() -> 2
// 进阶:

// 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
// 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

#include "../stdc++.h"

/* 简单排序 - 超时
时间复杂度：O(nlogN)
空间复杂度：O(n)
*/
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        store.push_back(num);
    }
    
    double findMedian() {
        sort(store.begin(), store.end());
        int n = store.size();
        return (n & 1 ? store[n/2] : (store[n/2 - 1] + store[n/2]) * 0.5);
    }
private:
    vector<double> store{};
};

/* 插入排序
时间复杂度：O(n)
空间复杂度：O(n)
*/
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (store.empty()) {
            store.push_back(num);
        } else {
            store.insert(lower_bound(store.begin(), store.end(), num), num);
        }
    }
    
    double findMedian() {
        int n = store.size();
        return (n & 1 ? store[n/2] : (store[n/2 - 1] + store[n/2]) * 0.5);
    }
private:
    vector<int> store{};
};

/* 两个堆
时间复杂度：O(logN)
空间复杂度：O(n)
*/
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return static_cast<double>(maxHeap.top());
        }
        return static_cast<double>((maxHeap.top() + minHeap.top()) * 0.5); // 不要用 /2
    }
private:
    priority_queue<int> maxHeap{}; // 默认大根堆，堆顶为最大值
    priority_queue<int, vector<int>, greater<int>> minHeap{};
};

// 有序集合
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
        int n = nums.size();
        nums.insert(num);
        if (n == 0) {
            left = nums.begin();
            right = nums.begin();
        } else if (n & 1) { // n是奇数
            if (num < *left) {
                --left;
            } else {
                ++right;
            }
        } else { // n是偶数
            if (num > *left && num < *right) {
                ++left;
                --right;
            } else if (num >= *right) {
                ++left;
            } else {
                --right;
                left = right;
            }
        }
    }
    
    double findMedian() {
        return 0.5 * (*left + *right);
    }
private:
    multiset<int> nums;
    multiset<int>::iterator left{nums.end()};
    multiset<int>::iterator right{nums.end()};
};
